# -*- coding: utf-8 -*-

"""剑指 Offer II 046. 二叉树的右侧视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:
输入: [1,null,3]
输出: [1,3]

示例 3:
输入: []
输出: []

提示:
二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100 """

from collections import deque

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """比前两题还简单"""
    def rightSideView(self, root: TreeNode) -> list:
        if not root:
            # 提交的时候谜之错误，输入root=[], 输出null，本地测试[]
            return []

        right_side, rightmost, taskque = [], root, deque([root])
        while True:
            try:
                node = taskque.popleft()
                if node.left:
                    taskque.append(node.left)
                if node.right:
                    taskque.append(node.right)
                
                if rightmost is node:
                    right_side.append(rightmost.val)
                    rightmost = taskque.pop()
                    taskque.append(rightmost)
            except IndexError:
                break
        return right_side


if __name__ == '__main__':
    foo = []
    print(type(foo))
    if not foo:
        print(type(foo))
